package com.company.heap;

import java.util.ArrayList;

/**
 * Created by v on 16-12-7.
 */
public class MinHeap <E extends Comparable<E>>{
    private ArrayList<E> list=new ArrayList<E>();

    public MinHeap(){}

    public MinHeap(E[] e){
        for(int i=0;i<e.length;i++){
            list.add(e[i]);
        }
        buildHeap();
    }

    //插入堆
    public void add(E e){
        list.add(e);
        int current=list.size()-1;
        while (current>0){
            int parent=(current-1)>>1;
            if(list.get(parent).compareTo(list.get(current))>0){
                E temp=list.get(current);
                list.set(current,list.get(parent));
                list.set(parent,temp);
                current=parent;
            }else {
                break;
            }
        }
    }

    //从堆中pop一个元素
    public E remove(){
        //存下返回值
        E maxElement=list.get(0);

        //对头结点进行删除
        list.set(0,list.get(list.size()-1));
        list.remove(list.size()-1);

        //调节堆的平衡
        percolateDown(0);

        return maxElement;
    }

    //构造堆
    public void buildHeap(){
        for(int i=list.size()>>1;i>0;i--){
            percolateDown(i-1);
        }
    }

    //下滑调整操作,index表示其所对应的需要下滑的位点
    private void percolateDown(int index){
        while (index<list.size()){
            int leftChild=(index<<1)+1;
            int rightChild=(index<<1)+2;

            if(leftChild>=list.size()){
                break;
            }

            int minChild=leftChild;

            if(rightChild<list.size()
                    &&list.get(rightChild).compareTo(list.get(leftChild))<0){
                minChild=rightChild;
            }

            if(list.get(minChild).compareTo(list.get(index))<0){
                E temp=list.get(minChild);
                list.set(minChild,list.get(index));
                list.set(index,temp);
                index=minChild;
            }else {
                break;
            }
        }
    }

}
